package pl.mmadej.ds4java.ds.tree.twothree;

import pl.mmadej.ds4java.ds.common.DataStructure;
import pl.mmadej.ds4java.ds.queue.LinkedListQueue;
import pl.mmadej.ds4java.ds.queue.Queue;
import pl.mmadej.ds4java.ds.stack.ArrayStack;
import pl.mmadej.ds4java.ds.stack.Stack;
import pl.mmadej.ds4java.ds.tree.Tree;

public class TwoThreeTree<T extends Comparable<T>> extends DataStructure<T> implements Tree<T> {

    @SuppressWarnings("unchecked")
    private MultiValueNode<T> root = new MultiValueNode<T>();
    private int noOfElements;

    @Override
    public boolean insert(T elementToInsert) {
        MultiValueNode<T> nodeForNewElement = findNodeForElement(elementToInsert);
        if (nodeForNewElement.containsValue(elementToInsert)) {
            return false;
        }
        putElementIntoNodeInProperOrder(nodeForNewElement, elementToInsert);
        splitIfHasMoreThanThreeValues(nodeForNewElement);
        noOfElements++;
        return true;
    }

    private MultiValueNode<T> findNodeForElement(T element) {
        //finds potential parent or node with given element
        MultiValueNode<T> nodeForElement = root;
        while (nodeForElement.isNotLeaf() && nodeForElement.doesNotContainValue(element)) {
            nodeForElement = returnChildNodeWhichIsAncestorOfNewElement(nodeForElement, element);
        }
        return nodeForElement;
    }

    private void putElementIntoNodeInProperOrder(MultiValueNode<T> node, T elementToInsert) {
        int index = findIndexForElement(node, elementToInsert);
        node.insertValueAt(index, elementToInsert);
    }

    private void splitIfHasMoreThanThreeValues(MultiValueNode<T> node) {
        while (hasMoreThanThreeValues(node)) {
            node = splitNodeAndReturnParentForSiblingsFromSplit(node);
        }
    }

    private MultiValueNode<T> returnChildNodeWhichIsAncestorOfNewElement(MultiValueNode<T> node, T elementToInsert) {
        int index = findIndexForElement(node, elementToInsert);
        return node.getChildAt(index);
    }

    private int findIndexForElement(MultiValueNode<T> node, T element) {
        int index = 0;
        for (T value : node.getValues()) {
            if (elementToInsertIsSmallerOrEqualToNodeValue(element, value)) {
                return index;
            }
            index++;
        }
        return index;
    }

    private boolean elementToInsertIsSmallerOrEqualToNodeValue(T elementToInsert, T nodeValue) {
        return elementToInsert.compareTo(nodeValue) < 0;
    }

    @SuppressWarnings("unchecked")
    private MultiValueNode<T> splitNodeAndReturnParentForSiblingsFromSplit(MultiValueNode<T> nodeToSplit) {
        //parent is always with one value here
        T middleValue = nodeToSplit.getValueAt(1);
        T leftParentValue = nodeToSplit.getValueAt(0);
        T rightParentValue = nodeToSplit.getValueAt(2);
        MultiValueNode<T> parent = nodeToSplit.getParent();
        MultiValueNode<T> newRightParent = new MultiValueNode<T>(rightParentValue);
        MultiValueNode<T> newLeftParent = new MultiValueNode<T>(leftParentValue);

        if (parent == null) {//root
            parent = root = new MultiValueNode<T>(middleValue);
            addChildrenStartingAt(parent, newLeftParent, newRightParent);
        } else {
            int indexOfNodeAtParent = parent.indexOfChild(nodeToSplit);
            parent.insertValueAt(indexOfNodeAtParent, middleValue);
            parent.insertChildAt(indexOfNodeAtParent, newRightParent);
            parent.insertChildAt(indexOfNodeAtParent, newLeftParent);
            newLeftParent.setParent(parent);
            newRightParent.setParent(parent);
        }
        if (nodeToSplit.isNotLeaf()) {
            placeNodeChildrenInNewParents(nodeToSplit, newRightParent, newLeftParent);
        }
        parent.deleteChild(nodeToSplit);
        return parent;
    }

    @SuppressWarnings("unchecked")
    private void placeNodeChildrenInNewParents(MultiValueNode<T> node, MultiValueNode<T> rightParent, MultiValueNode<T> leftParent) {
        //place node children in new parents (left and right nodes)
        addChildrenStartingAt(leftParent, node.getChildAt(0), node.getChildAt(1));
        addChildrenStartingAt(rightParent, node.getChildAt(2), node.getChildAt(3));
    }

    private void addChildrenStartingAt(MultiValueNode<T> parent, MultiValueNode<T>... children) {
        for (MultiValueNode<T> child : children) {
            parent.insertChild(child);
            child.setParent(parent);
        }
    }

    private boolean hasMoreThanThreeValues(MultiValueNode<T> node) {
        return node.getValues().size() == 3;
    }

    @Override
    public boolean contains(T element) {
        return findNodeForElement(element).containsValue(element);
    }


    @Override
    public boolean delete(T element) {
        return false;
    }

    @Override
    public int numberOfElements() {
        return noOfElements;
    }

    @Override
    @SuppressWarnings("unchecked")
    public <E> E[] levelOrder(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray, noOfElements);

        int index = 0;
        Queue<MultiValueNode<T>> nodeQueue = new LinkedListQueue<MultiValueNode<T>>();
        nodeQueue.enqueue(root);
        while (!nodeQueue.empty()) {
            MultiValueNode<T> node = nodeQueue.dequeue();
            for (T value : node.getValues()) {
                resultArray[index++] = (E) value;
            }
            enqueueChildren(nodeQueue, node);
        }
        return resultArray;
    }

    private void enqueueChildren(Queue<MultiValueNode<T>> elementsToCheck, MultiValueNode<T> node) {
        for (MultiValueNode<T> child : node.getChildren()) {
            elementsToCheck.enqueue(child);
        }
    }


    @Override
    @SuppressWarnings("unchecked")
    public <E> E[] preOrder(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray, noOfElements);
        int arrayIndex = 0;
        Stack<MultiValueNode<T>> stack = new ArrayStack<MultiValueNode<T>>(noOfElements);
        stack.push(root);
        while (!stack.empty()) {
            MultiValueNode<T> node = stack.pop();
            for (int valueIndex = 0; valueIndex < node.getValuesCount(); valueIndex++) {
                resultArray[arrayIndex++] = (E) node.getValueAt(valueIndex);
            }
            for (int childIndex = node.getChildrenCount() - 1; childIndex >= 0; childIndex--) {
                stack.push(node.getChildAt(childIndex));
            }
        }
        return resultArray;
    }

    @Override
    @SuppressWarnings("unchecked")
    //using additional queue, maybe not so memory efficient but nice ;-)
    public final <E> E[] postOrder(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray, noOfElements);
        Stack<T> values = new ArrayStack<T>(noOfElements);
        Stack<MultiValueNode<T>> stack = new ArrayStack<MultiValueNode<T>>(noOfElements);
        stack.push(root);
        while (!stack.empty()) {
            MultiValueNode<T> node = stack.pop();
            for (int valueIndex = node.getValuesCount() - 1; valueIndex >= 0; valueIndex--) {
                values.push(node.getValueAt(valueIndex));
            }
            for (int childIndex = 0; childIndex < node.getChildrenCount(); childIndex++) {
                stack.push(node.getChildAt(childIndex));
            }
        }
        int arrayIndex = 0;
        while (!values.empty()) {
            resultArray[arrayIndex++] = (E) values.pop();
        }
        return resultArray;
    }
}
